#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
long long qmi(long long a,int b)
{
	long long res = 1;
	while(b)
	{
		if(b & 1) (res *= a) %= mod;
		(a *= a) %= mod;
		b >>= 1;
	}
	return res;
}
long long fac[5011],exfac[5011];
long long C(int n,int m)
{
	return fac[n] * exfac[m] % mod * exfac[n - m] % mod;
}
bool b[20000011];
int cnt = 0;
int mi[11];
int n;
int a[5011];
void DFS(int x)
{
	if(b[x])
		return;
	b[x] = 1,cnt++;
	for(int i = 1;i < n;i++) if(a[i] != a[i + 1])
	{
		int p = (a[i] < a[i + 1] ? i : i + 1),mn = min(a[i],a[i + 1]),mx = max(a[i],a[i + 1]);
		x += (mx - mn) * mi[n - p];
		a[p] = mx;
		DFS(x);
		x -= (mx - mn) * mi[n - p];
		a[p] = mn;
	}
}
int f[5011][5011];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("after.in","r",stdin);
	freopen("after.out","w",stdout);
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	fac[0] = 1;
	for(int i = 1;i <= n;i++)
		fac[i] = fac[i - 1] * i % mod;
	exfac[n] = qmi(fac[n],mod - 2);
	for(int i = n;i;i--)
		exfac[i - 1] = exfac[i] * i % mod;
	if(n <= 8)
	{
		mi[0] = 1;
		int x = 0;
		for(int i = 1;i <= n;i++)
			x = x * n + (--a[i]),mi[i] = mi[i - 1] * n;
		DFS(x);
		cout << cnt;
		return 0;
	}
	f[n][n] = 1;
	for(int i = n - 1;i;i--)
		for(int j = n;j >= i;j--)
			(f[i][j] = f[i][j + 1] + f[i + 1][j]) %= mod;
	for(int i = 1;i <= n;i++)
		(cnt += f[1][i]) %= mod;
	cout << cnt;
	return 0;
}
